While the problem of scheduling a plurality of concurrent and timed job sequences with constraints of mutual delay and mutual exclusion with allowed bounded time slacks can be applied to a large variety of contexts, in the present application, without loss of generality, we address the problem with reference to a concrete example of a run-time scheduler for an electromechanical system for biological analyses, such as for example the VIDAS system engineered by bioMérieux
The system of the present example is able to run a group of multiple concurrent analyses, each alternating steps of biological reaction of the sample and transfer operations carried out by shared electro-mechanical devices; the duration of each reaction step is determined by the biological protocol of the analysis, but bounded waiting times can be added after the completion of each reaction step. This gives raise to the scheduling problem of determining waiting times after each step so as to comply with maximum allowed delays and to avoid conflicts in the usage of shared resources, while maximizing the number of concurrent analyses and minimizing their overall completion time.
With more detail, each type of biological analysis is comprised by a pretreatment phase and an analytic protocol. At the beginning of the analysis, the sample is contained in a test-tube uniquely identified by a barcode, while other tubes contain dilution and incubation fluids and other tubes are empty. During the pretreatment phase, an automatic pipettor repeatedly pours off the sample among the various tubes; each pipettor action lasts for a deterministic amount of time. Waiting times are allowed between successive actions, but they are constrained to range between minimum and maximum values determined by incubation/reaction periods and sample deterioration properties. After completion of the pretreatment phase, the analytic protocol follows a fixed sequence of steps during which the sample is combined with reagents and multiple measurements are taken by a read-head whose operations take deterministic durations (see FIG. 1).
For efficient exploitation of electromechanical components, multiple analyses, possibly of different types, are carried out concurrently. To this end, the system composes multiple sections, one for each analysis. Each section is in turn divided in slots, carrying different samples that can be subject to different pretreatments and can operate on samples of different subjects. However, since the read-head is designed to take measures on a whole section at once, all slots in the same section are constrained to run the same analytic protocol (see FIG. 2).
The pipettor and the read-head are shared among different slots and sections and cannot be used simultaneously by two different analyses. This raises a scheduling problem that must determine feasible values of the initial delay of each pretreatment and waiting times between events of the same analysis. Such values must avoid the need of contemporary actions of the pipettor and the read-head, avoid waiting times beyond allowed bounds and keep the overall time span of the group of analyses as short as possible.
Problem Formulation
The problem can be formally cast in the general notation of job shop scheduling as a set of n independent and non-preemptible jobs J1 . . . Jn, with release times r1 . . . rn and deterministic Execution Times e1 . . . en, each job being statically assigned to one out of m independent machines M1 . . . Mm, subject to constraints of precedence and mutual exclusion:                for any two jobs Ji and Jk, a precedence constraint may require that the delay between the completion of Jk and the start of Ji range within a minimum d−ik and a maximum d+ik:d−ik≦ri−(rk+ek)d+ik         for any two jobs Ji and Jk, a mutual exclusion constraint may require that the execution periods of Jk and Ji do not overlap; this may be achieved with either of the following two determinations, which guarantee that Ji starts after completion of Jk or viceversa:ri≧rk+ek OR ri+ei≦rk         
The scheduling problem amounts to determine the release times r1 . . . rn, subject to all prescribed precedence and mutual exclusion constraints, so as to minimize the completion time of the overall plurality of job sequences. FIG. 3a illustrates an instance of the problem: Jobs J1, J2, J3, and J4 are allocated on Machines M1 and M2; Job J2 has a mutual exclusion with respect to J4 and a precedence constraint bounding its start time with respect to the completion time of J1 and J3. A precedence constraints also bounds the delay of the start time of J4 with respect to the completion of J3. FIG. 3b shows a solution for the problem.
The scheduling problem defined above is characterized by the intertwining of non-deterministic release times with mutual exclusion and precedence constraints, and it can thus be conveniently formulated on the ground of non-deterministic formalisms such as Time Petri Nets (TPN) or Timed Automata (TA) through a direct translation of scheduling concepts like jobs, constraints and resources, into places/locations, transitions, pre- and post-conditions. This opens the way to the application of modeling and verification tools that manage the combination of concurrency constraints and non-deterministic timers through symbolic analysis of the state space based on Regions (see R. Alur, D. L. Dill: Automata for modeling real-time systems. In Proc. Of 17th ICALP, 1990) or Difference Bounds Matrix (DBM) zones (see D. Dill. Timing Assumptions and Verification of Finite-State Concurrent Systems. In Proc. Workshop on Computer Aided Verification Methods for Finite State Systems, 1989). In this perspective, the scheduling problem can be formulated as the identification of a witness in the symbolic state space that satisfies a Real Time Model Checking formula (see e.g. A. Fehnker. Scheduling a steel plant with timed automata. In Real-Time Computing Systems and Applications, 1999. RTCSA '99. Sixth International Conference on, pages 280-286, 1999) that selects “all behaviors that reach a completion state within a maximum time T, after traversing only states without conflicts in the usage of resources”. The optimal value of T can be obtained through polynomial iteration, which is supported in various tools and notably in the Uppaal environment (see e.g. K. Larsen. Resource-efficient scheduling for real time systems. In Rajeev Alur and Insup Lee, editors, Embedded Software, volume 2855 of Lecture Notes in Computer Science, pages 16-19. Springer Berlin-Heidelberg, 2003.; or I. AlAttili, F. Houben, G. Igna, S. Michels, F. Zhu, and F. W. Vaandrager. Adaptive scheduling of data paths using uppaal tiga. In QFM, pages 1-11, 2009). In the Oris tool (G. Bucci and L. Carnevali and L. Ridi and E. Vicario. Oris: a Tool for Modeling, Verification and Evaluation of Real-Time Systems. International Journal of Software Tools for Technology Transfer, 12(5):391-403, 2010), the optimum value T is derived in direct manner by evaluating the minimum and maximum time spent along each sequence of transitions that satisfy the expected sequencing constraints (E. Vicario. Static Analysis and Dynamic Steering of Time Dependent Systems Using Time Petri Nets. IEEE Trans. on SW Eng., 27(1):728-748, August 2001).
Unfortunately, straight application of this type of symbolic state space analysis techniques faces the problems of state space explosion (as the number of states grows exponentially with the number of jobs) and curse of dimensionality (as the size of data structures encoding each state grows quadratically with the number of sequences). This results in memory and time complexity that are by far not affordable for an on-line scheduler, even if computation is performed on a conventional PC, which is often not the case in industrial applications.
Just to figure out the order of magnitude of practical complexity, state space analysis based on DBM zones with the Oris tool was experimented on the TPN representation of a simplistic case made of two Sections, three Slots per Section, and deterministic delays: the TPN enumeration procedure would produce a huge state space of 255128 DBM state classes, which requires about 20 minutes on a dual-core 2 GHz desktop computer, with 4216 possible paths from the initial state to the end terminal node.
Even applying state of the art techniques for reducing complexity through model simplification, end even partitioning the state space through DBM Zones (which are much more compact than Regions), processing times and memory demand of this class of state space analysis techniques are not compatible with the intended use within an industrial application as the one described above: this requires that the scheduling problem be solved on-line in a near-real-time approach, and that its execution be affordable within an embedded component that runs on limited processing and memory resources. Hardware resources normally available in this kind of biological testing machines (but more generally in industrial electromechanical machines) is very limited and not compatible with the huge demand of such a complex mathematical algorithm implementation.
A solution that could trade generality of analysis for efficiency in the specific problem so as to run faster and with lower demand of memory and processing power would be therefore highly desirable.